import java.util.ArrayList;

/*
剑指 Offer 62. 圆圈中最后剩下的数字
解题思路：递归、迭代
用一个list来保存数，根据(index + m - 1) % n来决定删除list中哪个元素
0 1 2 3 4
 */
public class Offer62 {

  public static void main(String[] args) {
    System.out.println(new Offer62().lastRemaining(5, 3));
  }

//  public int lastRemaining(int n, int m) {
//    int f = 0;
//    for (int i = 2; i <= n; i++) {
//      f = (m + f) % i;
//    }
//    return f;
//  }
//  public int lastRemaining(int n, int m) {
//    return f(n, m);
//  }
//
//  public int f(int n, int m) {
//    if (n == 1) {
//      return 0;
//    }
//    int x = f(n - 1, m);
//    return (m + x) % n;
//  }

  public int lastRemaining(int n,int m){
    ArrayList<Integer> list = new ArrayList<>();
    for (int i = 0; i < n; i++) {
      list.add(i);
    }
    int index = 0;
    while (n > 1){
      index = (index + m - 1) % n;
      list.remove(index);
      n--;
    }
    return list.get(0);
  }


}
